0658. 找到 K 个最接近的元素【中等】
1. 📝 题目描述
给定一个 排序好 的数组 arr，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x|或者|a - x| == |b - x|且a < b
示例 1：
txt
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]1
2
2
示例 2：
txt
输入：arr = [1,1,2,3,4,5], k = 4, x = -1
输出：[1,1,2,3]1
2
2
提示：
1 <= k <= arr.length1 <= arr.length <= 10^4arr按 升序 排列-10^4 <= arr[i], x <= 10^4
2. 🎯 s.1 - 二分查找
c
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
int lo = 0, hi = arrSize - k;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
else hi = mid;
}
int* res = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++) res[i] = arr[lo + i];
*returnSize = k;
return res;
}1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
js
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function (arr, k, x) {
let lo = 0,
hi = arr.length - k
while (lo < hi) {
const mid = (lo + hi) >> 1
if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1
else hi = mid
}
return arr.slice(lo, lo + k)
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
py
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
lo, hi = 0, len(arr) - k
while lo < hi:
mid = (lo + hi) // 2
if x - arr[mid] > arr[mid + k] - x:
lo = mid + 1
else:
hi = mid
return arr[lo:lo + k]1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
- 时间复杂度：
- 空间复杂度：
算法思路：
- 二分查找窗口的左端点，范围为
[0, n-k] - 比较
x到窗口左端和右端下一个元素的距离来决定移动方向